#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2005;
int u[MAXN], v[MAXN]; vector<int> G[MAXN]; int n;
int dis[MAXN][MAXN]; void getd(int s) {
	for (int i = 1; i <= n; i++) dis[s][i] = -1;
	dis[s][s] = 0; queue<int> q; q.push(s);
	while (q.empty() == 0) {
		int u = q.front(); q.pop(); for (int v : G[u]) {
			if (dis[s][v] == -1) dis[s][v] = dis[s][u] + 1, q.push(v);
		}
	}
}
int main() {
	freopen("oi.in", "r", stdin);
	freopen("oi.out", "w", stdout);
	int c, t; scanf("%d %d", &c, &t); while (t--) {
		int m; scanf("%d %d", &n, &m);
		for (int i = 1; i <= m; i++) scanf("%d %d", &u[i], &v[i]);
		if (n <= 5) {
			int rec = 0x3f3f3f3f, cn = 0;
			for (int _ = 1; _ < 1 << n * (n + 1) / 2; _++) {
				if (__builtin_popcount(_) != m - 1) continue;
				int f = 0; for (int i = 1; i <= n; i++) G[i].clear();
				for (int i = 1; i <= n; i++) for (int j = i + 1; j <= n; j++) {
					if (_ >> f++ & 1) G[i].push_back(j), G[j].push_back(i);
				}
				for (int i = 1; i <= n; i++) getd(i);
				int re = 0; bool fl = 0;
				for (int i = 1; i <= m; i++) {
					if (dis[u[i]][v[i]] == -1) {fl = 1; break;}
					re += dis[u[i]][v[i]];
				}
				if (fl) continue;
				if (rec > re) rec = re, cn = 1;
				else if (rec == re) cn++;
				// printf("%d -> %d %d(%d)\n", _, rec, cn, re);
			}
			printf("-%d %d\n", rec, cn);
		}
		else {
			int rec = 0x3f3f3f3f, cn = 0;
				int f = 0; for (int i = 1; i <= n; i++) G[i].clear();
				for (int i = 2; i <= m; i++) G[u[i]].push_back(v[i]), G[v[i]].push_back(u[i]);
				for (int i = 1; i <= n; i++) getd(i);
				int re = 0; bool fl = 0;
				for (int i = 1; i <= m; i++) {
					if (dis[u[i]][v[i]] == -1) {fl = 1; break;}
					re += dis[u[i]][v[i]];
				}
				if (fl) continue;
				if (rec > re) rec = re, cn = 1;
				else if (rec == re) cn++;
			printf("-%d %d\n", rec, cn);
		}
	}
}